#include <iostream>
#include "magicsquare.h"

Square::Square() {
	// create an empty square
	for (int row = 0; row < 4; row++) {
		for (int col = 0; col < 4; col++) {
			square[row][col] = 0;
		}
	}
	// mark all digits not used
	for (int dig = 0; dig < 10; dig++) {
		used[dig] = false;
	}
	numUsed = 0;
	// problem solving has really not yet begun
	lastRowTried = 1;
	lastColTried = 1;
	lastValTried = 0;
	firstRowTried = 1;
	firstColTried = 1;
	firstValTried = 0;
}


	// make sure the number isn't already being used
	// then if not put it in the requested position
	//  (if the position is empty)
bool Square::place(int row, int col, int val){ 
	// ensure not used already
	if (used[val]) {
		// already being used
		return false;
	}
	// if here we know that value is ok
	// check if position is ok
	if (!posOpen(row,col) ) {
		// already full
		return false;
	}
	// if we get here then it is ok
	square[row][col] = val;
	used[val] = true;
	numUsed++;
	lastRowTried = row;
	lastColTried = col;
	lastValTried = val;
	return true;
}

	// take out a placement
bool Square::unplace(int row, int col) {
	// find out what value is there
	int toClear = square[row][col];
	// make that value available again
	used[toClear] = false;
	// clear the spot
	square[row][col] = 0;
	// reduce number used
	numUsed--;
	// right now I'm not sure how this fails
	return true;
}

	// take out the most recent placement
bool Square::unplace() {
	used[lastValTried] = false;
	// clear the spot
	square[lastRowTried][lastColTried] = 0;
	// reduce number used
	numUsed--;
	// right now I'm not sure how this fails
	return true;
}

	// report value at a given position 
int  Square::getVal(int row, int col) {
	return square[row][col];
}


	// report if a given position is open
bool Square::posOpen(int row, int col) {
	// check if position is open
	if (square[row][col] == 0) {
		// position open
		return true;
	}
	else {
		return false;
	}
}


	// report if a given value is used
bool Square::valUsed(int val) {
	// ensure not used already
	if (used[val]) {
		// already being used
		return true;
	}
	else {
		return false;
	}
}


	// return the sum for a row
int Square::rowSum(int row) {
	int sum = 0;
	for (int col = 1; col < 4; col++){
		sum += square[row][col];
	}
	return sum;
}


	// return the sum for a column
int Square::colSum (int col) {
	int sum = 0;
	for (int row = 1; row < 4; row++){
		sum += square[row][col];
	}
	return sum;
}

	// return the sum for the left to right diag
int Square::diagLeftSum() {
	int sum = 0;
	for (int num = 1; num < 4; num++ ){
		sum += square[num][num];
	}
	return sum;
}

	// return the sum for the right to left diag
int Square::diagRightSum() {
	int sum = 0;
	for (int num = 1; num < 4; num++ ){
		sum += square[4-num][num];
	}
	return sum;
}


	// report whether the row is under value
bool Square::rowUnder (int row) {
	int correctSum = 15;
	int cnt = 0;
	int sum = 0;
	for (int col = 1; col < 4; col++){
		sum += square[row][col];
		if (square[row][col] > 0) {
			cnt++;
		}
	}
	// problem if all three values filled and under valued
	if (cnt == 3) {
		if (sum < correctSum) {
			return true;
		}
	}
	return false; // default to not under
}

	// report whether the col is under value
bool Square::colUnder (int col) {
	int correctSum = 15;
	int cnt = 0;
	int sum = 0;
	for (int row = 1; row < 4; row++){
		sum += square[row][col];
		if (square[row][col] > 0) {
			cnt++;
		}
	}
	// problem if all three values filled and under valued
	if (cnt == 3) {
		if (sum < correctSum) {
			return true;
		}
	}
	return false; // default to not under
}

	// report whether left diag is under value
bool Square::leftDiagUnder() {
	int correctSum = 15;
	int cnt = 0;
	int sum = 0;
	for (int n = 1; n < 4; n++){
		sum += square[n][n];
		if (square[n][n] > 0) {
			cnt++;
		}
	}
	// problem if all three values filled and under valued
	if (cnt == 3) {
		if (sum < correctSum) {
			return true;
		}
	}
	return false; // default to not under
}

	// report whether right diag is under value
bool Square::rightDiagUnder() {
	int correctSum = 15;
	int cnt = 0;
	int sum = 0;
	for (int n = 1; n < 4; n++){
		sum += square[4-n][n];
		if (square[4-n][n] > 0) {
			cnt++;
		}
	}
	// problem if all three values filled and under valued
	if (cnt == 3) {
		if (sum < correctSum) {
			return true;
		}
	}
	return false; // default to not under
}


	// check if the magic square is perfect
bool Square::checkSquare() {
	bool good = true;
	int correctSum = 15;
	/// check all rows
	for (int row = 1; row < 4; row++) {
		int sum = rowSum(row);
		if (sum != correctSum) {
			// not a perfect square
			good = false;
			return good;
		}
	}
	/// check all cols
	for (int col = 1; col < 4; col++) {
		int sum = colSum(col);
		if (sum != correctSum) {
			// not a perfect square
			good = false;
			return good;
		}
	}
	// check diagonals
	int sum = diagLeftSum();
	if (sum != correctSum) {
		// not a perfect square
		good = false;
		return good;
	}
	sum = diagRightSum();
	if (sum != correctSum) {
		// not a perfect square
		good = false;
		return good;
	}
	return good;
}


	// check if the (possibly partial) magic square is bad already
bool Square::badSquare() {
	bool bad = false;
	int correctSum = 15;
	/// check all rows
	for (int row = 1; row < 4; row++) {
		int sum = rowSum(row);
		if (sum > correctSum) {
			// already a bad square
			bad = true;
			return bad;
		}
		if (rowUnder(row) ) {
			bad = true;
			return bad;
		}
	}
	/// check all cols
	for (int col = 1; col < 4; col++) {
		int sum = colSum(col);
		if (sum > correctSum) {
			// already a bad square
			bad = true;
			return bad;
		}
		if (colUnder(col) ) {
			bad = true;
			return bad;
		}
	}
	// check diagonals
	int sum = diagLeftSum();
	if (sum > correctSum) {
			// already a bad square
			bad = true;
			return bad;
	}
	if (leftDiagUnder() ) {
		bad = true;
		return bad;
	}
	sum = diagRightSum();
	if (sum > correctSum) {
			// already a bad square
			bad = true;
			return bad;
	}
	if (rightDiagUnder() ) {
		bad = true;
		return bad;
	}
	return bad;
}

	// advance to next possible square - returning changed square
Square Square::nextPossSquare() {
	Square next = *this;
	int nextVal = next.lastValTried;
	int nextCol = next.lastColTried;
	int nextRow = next.lastRowTried;
	bool placed = false;
	int startRow = firstRowTried;
	int startCol = firstColTried;
	int startVal = firstValTried;
	// MAR - problem is that when we think we have a good place and come out of this function
	//    then the caller resets lastRowTried etc and so when we come back in here we are 
	//    restarting our starting point - so we never realize we have looped
	//    Probably need to bring stuff from nextNonBadSquare into here - DONE
	bool moved = false; // indicate haven't tried a new position yet
	bool loopedback = false; // indicate haven't gone back to beginning of positions yet
	// see if have already been working on problem and already looped around
	if ( (nextRow < startRow) || ((nextRow == startRow) && (nextCol < startCol) )
			|| (( nextRow == startRow) && (nextCol == startCol) && (nextVal < startVal)) ) {
		loopedback = true;
	}
	// loop until able to place a value in a position
	while (! placed) {
		//int nextVal = next.lastValTried + 1;
		nextVal++;
		// loop until position is open
		while ( ! next.posOpen(nextRow,nextCol) ) {
			nextVal = 1;
			moved = true;  // we know we have moved from our spot
			nextCol++;
			if (nextCol > 3) {
				nextCol = 1;
				nextRow = nextRow + 1;
				if (nextRow > 3) {
					nextRow = 1;
					if (loopedback) {
						// if already looped back once we  have trouble - bail!!
						cerr << "at end of road - finally " << endl;
						next.lastRowTried = 4; // caller uses this to know that we didn't find anything
						next.lastColTried = nextCol;
						next.lastValTried = nextVal;
						placed = true;  // prepare to get out of loop
						break;          // get out of inner loop
					}
					else {
						loopedback = true;  // we know we have looped back
					}
				} 
			}
		}
		// no use going to a lot of effort below if the numbers 
		// have already been used
		while ( next.valUsed(nextVal) && (nextVal <= 9) ) {
			nextVal++;
		}
		// see if went past highest possible value
		if (nextVal > 9) {
			// need to try a new position
			nextVal = 1;
			moved = true;  // we know we have moved from our spot
			nextCol = nextCol + 1;
			if (nextCol > 3) {
				nextCol = 1;
				nextRow = nextRow + 1;
				if (nextRow > 3) {
					nextRow = 1;
					if (loopedback) {
						// if already looped back once we  have trouble - bail!!
						cerr << "at end of road - finally " << endl;
						next.lastRowTried = 4; // caller uses this to know that we didn't find anything
						next.lastColTried = nextCol;
						next.lastValTried = nextVal;
						placed = true;  // prepare to get out of loop
						break;          // get out of inner loop
					}
					else {
						loopedback = true;  // we know we have looped back
					}
				} 
			}
		}
		// don't try to place if same as previously tried
		//if ((nextRow != startRow) || (nextCol != startCol) || (nextVal != startVal) ) {
		////////////////////////////////////////
		// see if went all of the way around
		/////////
		// went all the way around if have looped back to the beginning 
		//    and gone past the starting point
		// Have looped back if have moved from starting point and 
		//    reached a position lower than the starting position
		// Have moved if the row or column position has changed
		if (moved && loopedback && 
			((nextRow > startRow) || ((nextRow == startRow) && (nextCol > startCol) )
			|| (( nextRow == startRow) && (nextCol == startCol) && (nextVal >= startVal)) ) ) {
			/* 
			( (nextRow >= startRow) 
			&& (nextCol >= startCol)
			&& (nextVal >= startVal) ) ) {
			*/
			/*
			( (next.lastRowTried >= startRow) 
			&& (next.lastColTried >= startCol)
			&& (next.lastValTried >= startVal) ) ) {
			*/
		//if (nextRow > 3) {
			cerr << "at end of road" << endl;
			next.lastRowTried = 4; // caller uses this to know that we didn't find anything
			next.lastColTried = nextCol;
			next.lastValTried = nextVal;
			placed = true;  // get out of loop
			/*
		if ( loopedback && 
			( (next.lastRowTried >= startRow) 
			&& (next.lastColTried >= startCol)
			&& (next.lastValTried >= startVal) ) ) {
			atEnd = true;
		}
		if ( moved && ( ( next.lastRowTried <= startRow) 
			&& (next.lastColTried <= startCol) ) ) {
			loopedback = true;
		}
		if ( (next.lastRowTried != startRow)
			|| (next.lastColTried != startCol) {
			moved = true;
		} */
		}
		else {
			// only try to place if it is a real possibility
			if ( next.posOpen(nextRow,nextCol) && ! next.valUsed(nextVal) ) {
				// try placing - I think we don't really update next until place does its thing
				// try to place value in position
				bool bad;
				placed = next.place(nextRow,nextCol,nextVal);
				if (placed) {
					// see if placement is illegal
					bad = next.badSquare();
					if (bad) {
						// placement didn't work - get rid of placement
						bool ok = next.unplace();
						placed = false;
					} 
				}
				/*
			if (!placed) {
				// couldn't place - keep track
				next.lastRowTried = nextRow;
				next.lastColTried = nextCol;
				next.lastValTried = nextVal;
				}
				*/
			}
		}
		
	} // end while

	return next;
}



	// advance to next non-bad square - 
	//     - a square that doesn't already have a violation
	// returning changed square
Square Square::nextNonBadSquare() {
	bool found = false;
	bool atEnd = false;
	Square next = *this;
	while (( !found ) && ( ! atEnd) ) {
		// move to next placement
		next = next.nextPossSquare();
		// see if ran out of places to search
		atEnd = next.searchAtEnd();
		if (! atEnd ) {
			// see if placement is illegal
			bool bad = next.badSquare();
			if (! bad) {
				found = true;
			}
			else {
				// placement didn't work - get rid of placement
				bool ok = next.unplace();
			}
		}
	}
	return next;
}

		
	// report if beyond finding a value to place
bool Square::searchAtEnd() {
	if (lastRowTried > 3) {
		return true;
	}
	else {
		return false;
	}
}



	// output a textual representation of a Student
ostream & operator << (ostream & out, Square & aSquare) {
	for (int row = 1; row < 4; row++ ) {
		for (int col = 1; col < 4; col++) {
			out << " " << aSquare.getVal(row,col);
		}
		out << endl;
	}
	return out;
}